class Solution {
public:
    vector<int> father,rank;
    
    int find(int u){
        return u == father[u] ? u : find(father[u]);
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        
        if(rank[x] < rank[y]){
            swap(x,y);
        }
        
        if(rank[y] == rank[x]) rank[x] += 1;
        father[y] = x;
    }
    
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        father.resize(n);
        rank.resize(n,1);
        for(int i = 0;i < n;i++){
            father[i] = i;
        }
        
        unordered_map<string,int> ump;
        
        
        for (int i = 0; i < n; i++) {
            int m = accounts[i].size();
            for (int j = 1; j < m; j++) {
                string s = accounts[i][j];
                if (ump.find(s) == ump.end()) {
                    ump[s] = i;
                } else {
                    Union(i, ump[s]);
                }
            }
        }
        
        unordered_map<int,vector<string> > rec;
        
        for(auto& kv : ump){
            rec[find(kv.second)].push_back(kv.first);
        }
        
        vector<vector<string> > ret;
        for(auto& [name,emails] : rec){
            vector<string> temp(1,accounts[name][0]);
            sort(emails.begin(),emails.end());
            temp.insert(temp.end(),emails.begin(),emails.end());
            
            ret.push_back(temp);
        }
        
        return ret;
    }
};
